from typing import *


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sm = sum(nums)
        if sm & 1 == 1:
            return False
        dp = [False] * (sm // 2 + 1)
        dp[0] = True
        for i in range(len(nums)):
            for j in range(sm // 2, -1, -1):
                if dp[j] and j + nums[i] <= sm // 2:
                    dp[j + nums[i]] = True
        return dp[-1]


so = Solution()
print(so.canPartition([1, 5, 11, 5]))
